import java.util.ArrayList;
import java.util.Comparator;
import java.util.TreeSet;

public class LeetCode729 {
}

// 模拟思路
class MyCalendar {

    private ArrayList<int[]> arrayList;

    public MyCalendar() {
        arrayList = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        end--;
        for (int[] info : arrayList) {
            int l = info[0], r = info[1];
            if (start > r || end < l) {
                continue;
            }
            return false;
        }
        arrayList.add(new int[]{start, end});
        return true;
    }

}

// 二分查找思路
class MyCalendar1 {

    private TreeSet<int[]> booked;

    public MyCalendar1() {
        // 使 TreeSet有序
        booked = new TreeSet<>((a, b) -> a[0] - b[0]);
    }

    public boolean book(int start, int end) {
        if (booked.isEmpty()) {
            booked.add(new int[]{start, end});
            return true;
        }
        // 设置二分查找开始的数
        int[] tmp = {end, 0};
        // 找到一个最接近 end 的区间
        int[] lower = booked.lower(tmp);
        // 如果没找到这个区间 或者 区间中的结束值小于等于 新日历的开始值则 True
        if (lower == null || start >= lower[1]) {
            booked.add(new int[]{start, end});
            return true;
        }
        return false;
    }
}
